package com.platform.modules.alg.alglib.poj1011;

import java.util.Arrays;
import java.util.Collections;

public class Poj1011 {
    public String output = "";
    private final int maxn = 70;
    private int n;
    private Integer stick[] = new Integer[maxn];
    private boolean used[] = new boolean[maxn];

    public Poj1011() {
        for (int i = 0; i < stick.length; i++) {
            stick[i] = 0;
        }
    }

    boolean dfs(int len, int InitLen, int index, int num) {
        if (num == n)
            return true;
        int prelen = -1;
        for (int i = index; i < n; i++) {
            if (used[i] || stick[i] == prelen)//已使用或与上一个未使用的木棒长度相同
                continue;
            used[i] = true;
            if (len + stick[i] < InitLen) {
                if (dfs(len + stick[i], InitLen, i + 1, num + 1))
                    return true;
                else
                    prelen = stick[i];
            } else if (len + stick[i] == InitLen) {
                if (dfs(0, InitLen, 0, num + 1))
                    return true;
                else
                    prelen = stick[i];
            }
            used[i] = false;//回溯复位
            if (len == 0)
                break;
        }
        return false;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        int n = Integer.parseInt(line[0]);
        String[] words = line[1].split(" ");
        Integer sumlen = 0;
        for (int i = 0; i < n; i++) {
            stick[i] = Integer.parseInt(words[i]);
            sumlen += stick[i];
            used[i] = false;
        }
        Arrays.sort(stick, Collections.reverseOrder());

        int maxlen = stick[0];
        boolean flag = false;
        for (Integer InitLen = maxlen; InitLen <= sumlen / 2; InitLen++) {
            if (sumlen % InitLen == 0 && dfs(0, InitLen, 0, 0)) {
                output = InitLen.toString();
                flag = true;
                break;
            }
        }
        if (!flag)
            output = sumlen.toString();
        return output;
    }
}
